/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/unique-paths-iii
   @Language: C++
   @Datetime: 19-07-01 18:55
   */

// DFS, Time 0ms
class Solution {
	int dfs(vector<vector<int>>& grid, int r, int c, int n){
		if(r<0 || r>=grid.size() || c<0 || c>=grid[r].size() || grid[r][c]==-1) return 0;
		if(grid[r][c]==2) return n==0?1:0;
		grid[r][c]=-1;
		int sum=dfs(grid,r+1,c,n-1)+dfs(grid,r-1,c,n-1)+dfs(grid,r,c+1,n-1)+dfs(grid,r,c-1,n-1);
		grid[r][c]=0;
		return sum;
	}
public:
	int uniquePathsIII(vector<vector<int>>& grid) {
		int step=1, r=0, c=0;
		for(int i=0; i<grid.size(); ++i)
			for(int j=0; j<grid[i].size(); ++j)
				if(grid[i][j]==1) r=i, c=j;
				else if(grid[i][j]==0) ++step;
		return dfs(grid,r,c,step);
	}
};
